{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographically Smallest Beautiful String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestBeautifulString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字典序最小的美丽字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个字符串满足以下条件，则称其为 <strong>美丽字符串</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它由英语小写字母表的前 <code>k</code> 个字母组成。</li>\n",
    "\t<li>它不包含任何长度为 <code>2</code> 或更长的回文子字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的美丽字符串 <code>s</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你找出并返回一个长度为 <code>n</code> 的美丽字符串，该字符串还满足：在字典序大于 <code>s</code> 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。</p>\n",
    "\n",
    "<p>对于长度相同的两个字符串 <code>a</code> 和 <code>b</code> ，如果字符串 <code>a</code> 在与字符串 <code>b</code> 不同的第一个位置上的字符字典序更大，则字符串 <code>a</code> 的字典序大于字符串 <code>b</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abcd\"</code> 的字典序比 <code>\"abcc\"</code> 更大，因为在不同的第一个位置（第四个字符）上 <code>d</code> 的字典序大于 <code>c</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcz\", k = 26\n",
    "<strong>输出：</strong>\"abda\"\n",
    "<strong>解释：</strong>字符串 \"abda\" 既是美丽字符串，又满足字典序大于 \"abcz\" 。\n",
    "可以证明不存在字符串同时满足字典序大于 \"abcz\"、美丽字符串、字典序小于 \"abda\" 这三个条件。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"dc\", k = 4\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>可以证明，不存在既是美丽字符串，又字典序大于 \"dc\" 的字符串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>4 &lt;= k &lt;= 26</code></li>\n",
    "\t<li><code>s</code> 是一个美丽字符串</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographically-smallest-beautiful-string](https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographically-smallest-beautiful-string](https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcz\"\\n26', '\"dc\"\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m',\n",
    "                    'n','o','p','q','r','s','t','u','v','w','x','y','z'][:k]\n",
    "        # 最理想的是，最后一个字符增大，还不是回文\n",
    "        \n",
    "        for _idx in range(len(s)-1, -1, -1):\n",
    "            #print(f'当前_idx={_idx}', s[_idx])\n",
    "            sort_  = letters.index(s[_idx])\n",
    "            left = s[:_idx]\n",
    "            right = s[_idx+1:]\n",
    "            flag1 = False\n",
    "            if sort_ == k-1:#这个字符没有空间了，前一个\n",
    "                #print('当前字符没空间')\n",
    "                continue\n",
    "            # new_c =  letters[sort_+1]\n",
    "            # new_c的选择范围 包括：大于当前sort，且和left的最后两个均不相同的最小的\n",
    "            # /right其实不用管，反正会完全重构\n",
    "            if len(left)==0:\n",
    "                del1 = set(s[_idx])\n",
    "            elif len(left)==1:\n",
    "                del1 = set([s[_idx], left[-1]])\n",
    "            else:\n",
    "                del1 = set([s[_idx], left[-1], left[-2]])\n",
    "            \n",
    "            #print(f'当前字符{s[_idx]} sort',sort_, del1)\n",
    "            for i in letters[sort_+1:]:#大于当前sort\n",
    "                #print(f'尝试换为{i}')\n",
    "                if i not in del1:\n",
    "                    flag1 = True\n",
    "                    new_c = i\n",
    "                    break\n",
    "            \n",
    "            if not flag1:# 这个换不了，直接下一个\n",
    "                #print(f'当前i={_idx}换不了')\n",
    "                continue\n",
    "\n",
    "            now_left = left+new_c\n",
    "            # print(f'尝试换掉{_idx}, left={left}, new_c={new_c}, right={right}, now_left={now_left}')\n",
    "            #提前换掉了一个更大的，那么right部分可以怎么小怎么安排了 从0开始,非回文即可\n",
    "            \n",
    "            #只用依次换成k个字母中除了和now_left的最后两个均不相同的min即可\n",
    "            for idx_right in range(len(right)):\n",
    "                if len(now_left) == 1: \n",
    "                    del_ = set(now_left[-1])\n",
    "                else:\n",
    "                    del_ = set([now_left[-1], now_left[-2]])\n",
    "                flag2 = False\n",
    "                for j in letters:#每一个都从最小的开始\n",
    "                    if j not in del_:\n",
    "                        now_left += j\n",
    "                        flag2 = True\n",
    "                        # print(f'right中{idx_right}替换成功，now_left={now_left}')\n",
    "                        break                    \n",
    "                if not flag2:#出现了right中的一个替换失败了, 尝试flag1新的呗\n",
    "                    # print('right部分替换失败了, 尝试flag1新的')\n",
    "                    continue\n",
    "            # print('llll',len(now_left),len(s), len(now_left) == len(s))\n",
    "            if len(now_left) == len(s):#全部完成了替换\n",
    "                return now_left\n",
    "\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        i = n - 1\n",
    "        ans = list()\n",
    "        for i in range(n):\n",
    "            ans.append(s[i])\n",
    "        # while i > 0:\n",
    "        #     if s[i] < s[i - 1]:\n",
    "        #         break\n",
    "        #     i -= 1\n",
    "        # print(i)\n",
    "        j = 1\n",
    "        while True:\n",
    "            while (i > 0 and ord(s[i]) + j == ord(s[i - 1])) or (i > 1 and ord(s[i]) + j == ord(s[i - 2])):\n",
    "                j += 1\n",
    "            if ord(s[i]) + j >= ord(\"a\") + k:\n",
    "                i -= 1\n",
    "                j = 1\n",
    "                if i < 0:\n",
    "                    return \"\"\n",
    "            else:\n",
    "                break\n",
    "        ans[i] = chr(ord(s[i]) + j)\n",
    "        # print(ans)\n",
    "        # print(i)\n",
    "        x = i + 1\n",
    "        while x < n:\n",
    "            ans[x] = \"a\"\n",
    "            j = 0\n",
    "            while (x > 0 and ord(ans[x]) + j == ord(ans[x - 1])) or (x > 1 and ord(ans[x]) + j == ord(ans[x - 2])):\n",
    "                j += 1\n",
    "            ans[x] = chr(ord(\"a\") + j)\n",
    "            x += 1\n",
    "        return \"\".join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        a = ord('a')\n",
    "        k += a\n",
    "        s = list(map(ord, s))\n",
    "        n = len(s)\n",
    "        i = n - 1\n",
    "        s[i] += 1  # 从最后一个字母开始\n",
    "        while i < n:\n",
    "            if s[i] == k:  # 超过范围\n",
    "                if i == 0: return \"\"  # 无法进位\n",
    "                # 进位\n",
    "                s[i] = a\n",
    "                i -= 1\n",
    "                s[i] += 1\n",
    "            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:\n",
    "                s[i] += 1  # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]\n",
    "            else:\n",
    "                i += 1  # 检查 s[i] 是否和后面的字符形成回文串\n",
    "        return ''.join(map(chr, s))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, x: str, k: int) -> str:\n",
    "        n = len(x)\n",
    "        mchr = chr(ord('a') + k - 1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def f(a, b, c):\n",
    "            while c < mchr:\n",
    "                c = chr(ord(c) + 1)\n",
    "                if c != b and c != a:\n",
    "                    return True\n",
    "            return False\n",
    "        z = -1\n",
    "        if f('\\0', '\\0', x[0]):\n",
    "            z = 0\n",
    "        if n > 1 and f('\\0', x[0], x[1]):\n",
    "            z = 1\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            if f(x[i - 2], x[i - 1], x[i]):\n",
    "                z = i\n",
    "                break\n",
    "       \n",
    "        if z == -1:\n",
    "            return ''\n",
    "        s = list(x)\n",
    "        c = s[z]\n",
    "        if z > 0:\n",
    "            b = s[z - 1]\n",
    "        else:\n",
    "            b = '\\0'\n",
    "        if z > 1:\n",
    "            a = s[z - 2]\n",
    "        else:\n",
    "            a = '\\0'\n",
    "        while c < mchr:\n",
    "            c = chr(ord(c) + 1)\n",
    "            if c != b and c != a:\n",
    "                s[z] = c\n",
    "                break\n",
    "        for j in range(z + 1, n):\n",
    "            for c in 'abc':\n",
    "                if c != s[j - 1] and (j == 1 or c != s[j - 2]):\n",
    "                    s[j] = c\n",
    "                    break\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        s = list(map(ord, s))\n",
    "        n = len(s)\n",
    "        base = ord('a')\n",
    "        idx = n - 1 \n",
    "        s[idx] += 1\n",
    "        k += base \n",
    "        while idx < n:\n",
    "            if s[idx] >= k:\n",
    "                if idx == 0:\n",
    "                    return ''\n",
    "                s[idx] = base\n",
    "                s[idx - 1] += 1 \n",
    "                idx -= 1 \n",
    "            elif idx > 0 and s[idx] == s[idx - 1] or idx > 1 and s[idx] == s[idx - 2]:\n",
    "                s[idx] += 1 \n",
    "            else:\n",
    "                idx += 1 \n",
    "        return ''.join(list(map(chr, s)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        a = ord('a')\n",
    "        k += a\n",
    "        s = list(map(ord, s))\n",
    "        i = n - 1\n",
    "        s[i] += 1\n",
    "        while i < n:\n",
    "            if s[i] == k:\n",
    "                if i == 0:\n",
    "                    return ''\n",
    "                s[i] = a\n",
    "                i -= 1\n",
    "                s[i] += 1\n",
    "            elif (i>0 and s[i] == s[i-1]) or (i>1 and s[i] == s[i-2]):\n",
    "                s[i] += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return ''.join(map(chr, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "all_str='abcdefghijklmnopqrstuvwxyz'\n",
    "id2c={i:j for i,j in enumerate(all_str)}\n",
    "c2id={j:i for i,j in enumerate(all_str)}\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        ans=[c2id[c] for c in s]\n",
    "        n=len(s)\n",
    "        i=n-1\n",
    "        ans[i]+=1\n",
    "        while i<n:\n",
    "            if ans[i]==k:\n",
    "                if i==0:\n",
    "                    return ''\n",
    "                ans[i]=0\n",
    "                i-=1\n",
    "                ans[i]+=1\n",
    "            elif i and ans[i]==ans[i-1] or i>1 and ans[i]==ans[i-2]:\n",
    "                ans[i]+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ''.join(id2c[idx] for idx in ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        a = ord('a')\n",
    "        k += a\n",
    "        s = list(map(ord, s))\n",
    "        n = len(s)\n",
    "        i = n - 1\n",
    "        s[i] += 1  # 从最后一个字母开始\n",
    "        while i < n:\n",
    "            if s[i] == k:  # 超过范围\n",
    "                if i == 0: return \"\"  # 无法进位\n",
    "                # 进位\n",
    "                s[i] = a\n",
    "                i -= 1\n",
    "                s[i] += 1\n",
    "            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:\n",
    "                s[i] += 1  # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]\n",
    "            else:\n",
    "                i += 1  # 检查 s[i] 是否和后面的字符形成回文串\n",
    "        return ''.join(map(chr, s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        #copy 0x3\n",
    "        a= ord('a')\n",
    "        k+= a\n",
    "        s= list(map(ord,s))\n",
    "        n = len(s)\n",
    "        i = n-1\n",
    "        s[i] += 1\n",
    "        while i <n:\n",
    "            if s[i] == k:\n",
    "                if i ==0:\n",
    "                    return ''\n",
    "                s[i]=a\n",
    "                i -=1 \n",
    "                s[i] += 1\n",
    "            elif i and s[i] == s[i-1] or i>1 and s[i] == s[i-2]:\n",
    "                s[i] += 1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ''.join(map(chr,s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        a = ord('a')\n",
    "        k += a\n",
    "        s = list(map(ord, s))\n",
    "        n = len(s)\n",
    "        i = n - 1\n",
    "        s[i] += 1  # 从最后一个字母开始\n",
    "        while i < n:\n",
    "            if s[i] == k:  # 超过范围\n",
    "                if i == 0: return \"\"  # 无法进位\n",
    "                # 进位\n",
    "                s[i] = a\n",
    "                i -= 1\n",
    "                s[i] += 1\n",
    "            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:\n",
    "                s[i] += 1  # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]\n",
    "            else:\n",
    "                i += 1  # 检查 s[i] 是否和后面的字符形成回文串\n",
    "        return ''.join(map(chr, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "一定要好好观察数据范围，有些数据范围暗示了一种简单的做法\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        a=ord('a')\n",
    "        k+=a  \n",
    "        s=list(map(ord,s))\n",
    "        n=len(s)  \n",
    "        i=n-1  \n",
    "        s[i]+=1\n",
    "        while i<n:\n",
    "            if s[i]==k:\n",
    "                if i==0:return \"\"\n",
    "                s[i]=a  \n",
    "                i-=1\n",
    "                s[i]+=1\n",
    "            elif i and s[i]==s[i-1] or i>1 and s[i]==s[i-2]:\n",
    "                s[i]+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ''.join(map(chr,s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        #copy 0x3\n",
    "        a= ord('a')\n",
    "        k+= a\n",
    "        s= list(map(ord,s))\n",
    "        n = len(s)\n",
    "        i = n-1\n",
    "        s[i] += 1\n",
    "        while i <n:\n",
    "            if s[i] == k:\n",
    "                if i ==0:\n",
    "                    return ''\n",
    "                s[i]=a\n",
    "                i -=1 \n",
    "                s[i] += 1\n",
    "            elif i and s[i] == s[i-1] or i>1 and s[i] == s[i-2]:\n",
    "                s[i] += 1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ''.join(map(chr,s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        s = list(map(ord, s))\n",
    "        n = len(s)\n",
    "        base = ord('a')\n",
    "        idx = n - 1 \n",
    "        s[idx] += 1\n",
    "        k += base \n",
    "        while idx < n:\n",
    "            if s[idx] >= k:\n",
    "                if idx == 0:\n",
    "                    return ''\n",
    "                s[idx] = base\n",
    "                s[idx - 1] += 1 \n",
    "                idx -= 1 \n",
    "            elif idx > 0 and s[idx] == s[idx - 1] or idx > 1 and s[idx] == s[idx - 2]:\n",
    "                s[idx] += 1 \n",
    "            else:\n",
    "                idx += 1 \n",
    "        return ''.join(list(map(chr, s)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        s = [ord(c)-96 for c in s]\n",
    "        ans = None\n",
    "        for i in range(len(s)):\n",
    "            ind = len(s)-i-1\n",
    "            cu = s[ind]\n",
    "            fr = s[ind-1] if ind > 0 else 0\n",
    "            frr = s[ind-2] if ind > 1 else 0\n",
    "            if cu == 26 or cu == k:continue\n",
    "            if cu+1 != fr and cu+1 != frr:\n",
    "                ans = s[:ind]\n",
    "                ans.append(cu+1)\n",
    "                break\n",
    "            elif cu == 25 or cu+1 == k:continue\n",
    "            elif cu+2 != fr and cu+2 != frr:\n",
    "                ans = s[:ind]\n",
    "                ans.append(cu+2)\n",
    "                break\n",
    "            elif cu == 24 or cu+2 == k: continue\n",
    "            else:\n",
    "                ans = s[:ind]\n",
    "                ans.append(cu+3)\n",
    "                break\n",
    "        if not ans: return ''\n",
    "        # print(ans)\n",
    "        la1 = ans[-1] if len(ans) > 0 else 0\n",
    "        la2 = ans[-2] if len(ans) > 1 else 0\n",
    "        for i in range(len(s)-len(ans)):\n",
    "            if 1 != la1 and 1!=la2:\n",
    "                ans.append(1)\n",
    "            elif 2 != la1 and 2!=la2:\n",
    "                ans.append(2)\n",
    "            else:\n",
    "                ans.append(3)\n",
    "            la2 = la1\n",
    "            la1 = ans[-1]\n",
    "        return ''.join([chr(n+96) for n in ans])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        ns = [ord(c) - ord('a') for c in s]\n",
    "        def find_smallest(cur, donts):\n",
    "            if cur + 1 < k and (cur + 1) not in donts:\n",
    "                return cur + 1\n",
    "            if cur + 2 < k and (cur + 2) not in donts:\n",
    "                return cur + 2\n",
    "            if cur + 3 < k:\n",
    "                return cur + 3\n",
    "            return None\n",
    "        \n",
    "        for i, v in reversed(list(enumerate(ns))):\n",
    "            change = find_smallest(v, ns[max(0, i - 2):i])\n",
    "            if change is not None: break\n",
    "        else:\n",
    "            return \"\"\n",
    "        \n",
    "        ns[i] = change\n",
    "\n",
    "        for j in range(i + 1, len(ns)):\n",
    "            ns[j] = find_smallest(-1, ns[max(0, j - 2):j])\n",
    "\n",
    "        return ''.join(chr(c + ord('a')) for c in ns)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestBeautifulString(self, s: str, k: int) -> str:\n",
    "        def dfs(pos: int, isLimit: bool, pre1: int, pre2: int):\n",
    "            if pos == n:\n",
    "                if not isLimit:\n",
    "                    yield path\n",
    "                return\n",
    "            lower = ords[pos] if isLimit else 97\n",
    "            for cur in range(lower, 97 + k):\n",
    "                if cur == pre1 or cur == pre2:\n",
    "                    continue\n",
    "                path.append(cur)\n",
    "                yield from dfs(pos + 1, (isLimit and cur == lower), cur, pre1)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        ords = list(map(ord, s))\n",
    "        res = next(dfs(0, True, 0, -1), [])\n",
    "        return \"\".join([chr(v) for v in res])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
